/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package ai;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

/**
 *
 * @author root
 */
public class ChartParser {
    
    public ChartParser(KnowledgeBase pKB){
        mKB = pKB;
    }
    
    public ParseNode parse(String pUserInput) throws ParseException{
            String lWords[] = pUserInput.toLowerCase().trim().split("\\s");
            mChart = new ArrayList<LinkedList<Edge>>(lWords.length + 1);
            for(int i = 0 ; i < (lWords.length +1) ;  i++){
                mChart.add(new LinkedList<Edge>());
            }
            
            Edge lEdge = new Edge(0, 0, "S'",null);
            lEdge.mUnknownLabels.add("S"); // OBS!!! Hard coded!
            addEdge(lEdge);
            for (int i = 0; i < lWords.length; i++){
                scanner(i, lWords[i]);
            }
            System.out.println(mChart.toString());
                        
            return generateParseTree(lWords);
    }
        
    private ParseNode generateParseTree(String pWords[]){
            LinkedList<String> lLabels = new LinkedList<String>();
            lLabels.add("S'");
            LinkedList<Edge> lEdgeList = findEdges(lLabels, 0, pWords.length);
            
            if(lEdgeList == null){
                System.out.println("I'm too stupid to understand that!");
                return null;
            }
            else{
                ParseNode lTop = new ParseNode("S'", 0, pWords.length, null);
                LinkedList<ParseNode> lPNodeList = new LinkedList<ParseNode>();
                lPNodeList.add(lTop);

                try{
                    generateChildNodes(lEdgeList, lPNodeList, pWords);
                }
                catch(NullPointerException e){
                    System.out.println("My knowledge in grammatics is far too limited to understand that.");
                }

                return lTop;
            }
    }
    
    private void generateChildNodes(LinkedList<Edge> pEdgeList, LinkedList<ParseNode> pPNodeList, String pWords[]){
            while (pEdgeList.isEmpty() == false){
                Edge lEdge = pEdgeList.pollFirst();
                ParseNode lPNode = pPNodeList.pollFirst();
                
                if (!mKB.isWordCategory(lEdge.mLeft)){
                    //System.out.println("Assert " + lEdge.mLeft + " == " + lPNode.getLabel());

                    //System.out.println("genChildNodes(), edge: " + lEdge);
                    LinkedList<Edge> lNewEdgeList = findEdges((LinkedList<String>)lEdge.mKnownLabels.clone(), lEdge.mStartIndex, lEdge.mEndIndex);
                    
                    //if(lNewEdgeList == null){
                    //    System.out.println("No children found for edge: " + lEdge);
                    //}
                  
                    //System.out.println("genChildNodes(), new edges: " + lNewEdgeList);
                    LinkedList<ParseNode> lNewPNodeList = new LinkedList<ParseNode>();

                    // Create child nodes.
                    for(Edge e : lNewEdgeList){
                        ParseNode lNewPNode = new ParseNode(e.mLeft, e.mStartIndex, e.mEndIndex, e.mSemanticExp);
                        
                        if(mKB.isWordCategory(e.mLeft)){
                            lNewPNode.setWord(pWords[e.mStartIndex]);
                        }
                        
                        //System.out.println("Adding node " + lNewPNode + " to node " + lPNode);
                        lPNode.addNode(lNewPNode);
                        lNewPNodeList.add(lNewPNode);
                    }

                    generateChildNodes(lNewEdgeList, lNewPNodeList, pWords);
                }
            }
    }
        
    private LinkedList<Edge> findEdges(LinkedList<String> pLabelList, int pStartIndex, int pEndIndex){
        //System.out.println("findEdges(" + pLabelList + ", " + pStartIndex + ", " + pEndIndex + ")");
        
        if (pLabelList.isEmpty()){
            if (pEndIndex == pStartIndex){
                //System.out.println("Terminating condition, returning empty list.");
                return new LinkedList<Edge>();
            }
            else{
                //System.out.println("Terminating condition, returning null.");
                return null;
            }
        }
        
        String lLabel = pLabelList.pollLast();
        
        if (mKB.isWordCategory(lLabel)){
            LinkedList<Edge> lResult = findEdges((LinkedList<String>)pLabelList.clone(), pStartIndex, pEndIndex-1);
            //System.out.println("findEdges(), wordcat: " + lLabel + ", LabelList: " + pLabelList + ", Result: " + lResult);

            if (lResult != null){
                lResult.add(new Edge(pEndIndex-1, pEndIndex, lLabel, null));
            }
            //System.out.println("Returning " + lResult);
            return lResult;
        }

        LinkedList<Edge> lEdgeList = mChart.get(pEndIndex);
        for(Edge e : lEdgeList){
            if (e.mLeft.equals(lLabel) && e.mUnknownLabels.isEmpty()){
                    //System.out.println("Testing edge: " + e);
                    LinkedList<Edge> lResult = findEdges((LinkedList<String>)pLabelList.clone(), pStartIndex, e.mStartIndex);
                    
                    if (lResult != null){
                        lResult.add(e);
                        return lResult;
                    }
            }
        }
        
        return null;
    }
    
    private void addEdge(Edge pEdge) throws ParseException{
        //System.out.println("addEdge: !isInChart(" + pEdge.mEndIndex + ", " + pEdge + ") == " + (!isInChart(pEdge.mEndIndex, pEdge)));
        if (!isInChart(pEdge.mEndIndex, pEdge)){
            //System.out.println("addEdge " + pEdge.toString());
            mChart.get(pEdge.mEndIndex).add(pEdge);
            if(pEdge.mUnknownLabels.isEmpty()){
                //System.out.println("addEdge " + pEdge.toString() + " -> extender");
                extender(pEdge);
            }
            else {
                //System.out.println("addEdge " + pEdge.toString() + " -> predictor");
                predictor(pEdge);
            }
        }
    }
    
    private void scanner(int j, String pWord) throws ParseException{
        LinkedList<Edge> lList = mChart.get(j);
        for(Edge e : lList){
            if(mKB.isWordInCategory(pWord, e.mUnknownLabels.peekFirst())){
                Edge lNewEdge = new Edge(e.mStartIndex, e.mEndIndex + 1, e.mLeft, e.mSemanticExp);
                lNewEdge.mKnownLabels = (LinkedList<String>)e.mKnownLabels.clone();
                lNewEdge.mUnknownLabels = (LinkedList<String>)e.mUnknownLabels.clone();
                lNewEdge.mKnownLabels.add(lNewEdge.mUnknownLabels.pollFirst());
                //System.out.println("scanner: Edge e = " + e + " found \"" + pWord + "\" in category " + e.mUnknownLabels.peekFirst() + " new edge: " + lNewEdge );
                addEdge(lNewEdge);
            }
            else{
                //System.out.println("scanner: Edge e = " + e + " did not find \"" + pWord + "\" in category " + e.mUnknownLabels.peekFirst() + "!!!");
            }
        }
    }
    
    private void predictor(Edge pEdge) throws ParseException{
        //System.out.println("predictor " + pEdge.toString());
        String lLabelToFind = pEdge.mUnknownLabels.peekFirst();
        LinkedList<SerialExp> lSerialExpList = mKB.findRewritesFor(lLabelToFind);
        //System.out.println("predictor rewrites " + lLabelToFind + " <- " + lSerialExpList.toString());
        for (SerialExp s : lSerialExpList){
            Edge lNewEdge = new Edge(pEdge.mEndIndex, pEdge.mEndIndex, lLabelToFind,s.mSemExp);
            for (LabelExp l : s.mExpList){
                lNewEdge.mUnknownLabels.add(l.getName());
            }
            //System.out.println("predictor new edge:" + lNewEdge.toString());
            addEdge(lNewEdge);
        }
    }
    
    private void extender(Edge pEdge) throws ParseException{
        int j = pEdge.mStartIndex;
        LinkedList<Edge> lList = mChart.get(j);
        for(Edge e : lList){
            if(pEdge.mLeft.equals(e.mUnknownLabels.peekFirst())){
                Edge lNewEdge = new Edge(e.mStartIndex, pEdge.mEndIndex, e.mLeft, e.mSemanticExp);
                lNewEdge.mKnownLabels = (LinkedList<String>)e.mKnownLabels.clone();
                lNewEdge.mUnknownLabels = (LinkedList<String>)e.mUnknownLabels.clone();
                /*for(String s : pEdge.mKnownLabels){
                    lNewEdge.mKnownLabels.add(s);
                }
                lNewEdge.mUnknownLabels.pollFirst()
                */
                lNewEdge.mKnownLabels.add(lNewEdge.mUnknownLabels.pollFirst());
                //System.out.println( "extender(" + pEdge + ") Edge e: " + e + " extended edge: " + lNewEdge  );
                addEdge(lNewEdge);
            }
        }
    }
    
    private boolean isInChart(int pChartIndex, Edge pEdge){
        LinkedList<Edge> lEdgeList = mChart.get(pChartIndex);
        
        for (Edge e : lEdgeList){
            if (e.equals(pEdge)){
                return true;
            }
        }
        return false;
    }
    
    private class Edge {
        
        public Edge(int pStart, int pEnd, String pLeft, SemanticExp pSemExp){
            mStartIndex = pStart;
            mEndIndex = pEnd;
            mLeft = pLeft;
            mSemanticExp = pSemExp;
            
            mKnownLabels = new LinkedList<String>();
            mUnknownLabels = new LinkedList<String>();
        }
        
        public boolean equals(Object o){
            if(o == null){
                return false;
            }
            //System.out.println("Edge: " + this.toString() + " equals  o.getClass() == Edge.class " + (o.getClass() == Edge.class));
            if(o.getClass() == Edge.class){
                Edge e = (Edge)o;
                if (this == o){
                    //System.out.println("Edge e == o true");
                    return true;
                }
                if(e.mStartIndex != mStartIndex || e.mEndIndex != mEndIndex){
                    return false;
                }
                if(!e.mLeft.equals(mLeft)){
                    return false;
                }
                if(!e.mKnownLabels.equals(mKnownLabels)){
                    return false;
                }
                if(!e.mUnknownLabels.equals(mUnknownLabels)){
                    return false;
                }
                return true;
            }
            return false;
        }
        
        private int getLabelCount(){
            return mKnownLabels.size() + mUnknownLabels.size();
        }
        public String toString(){
            if (mUnknownLabels.isEmpty()){
                return "(" + mStartIndex + "," + mEndIndex + ", " + mLeft + "<-" + mKnownLabels.toString() + " * " + mUnknownLabels.toString() + ")" ;
            }
            else {
                return "";
            }
        }
        
        public String mLeft;
        public LinkedList<String> mKnownLabels;
        public LinkedList<String> mUnknownLabels;
        public int mStartIndex;
        public int mEndIndex;
        public SemanticExp mSemanticExp = null;
    }
    
    private KnowledgeBase mKB;
    private ArrayList<LinkedList<Edge>> mChart;
}
